//TSP
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int inf=0x3fffffff;
const int maxn=10+2;
int mat[maxn][maxn], dp[1<<maxn][maxn];
int n;
int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        int i, j, k;
        memset(mat,0,sizeof(mat));
        for(i=0; i<=n; i++)
            for(j=0; j<=n; j++)
                scanf("%d",&mat[i][j]);
        for(k=0; k<=n; k++)//floyd求所有点对间的最短路
            for(i=0; i<=n; i++)
                for(j=0; j<=n; j++)
                    if(mat[i][j]>mat[i][k]+mat[k][j])
                        mat[i][j]=mat[i][k]+mat[k][j];
        int state;
        for(state=0; state<=(1<<n)-1; state++)//初始化
            for(i=0; i<=n; i++)
                dp[state][i]=inf;
        for(state=0; state<=(1<<n)-1; state++)
            for(i=1; i<=n; i++)
            {
                if( state&( 1<<(i-1) ) )                
				{
                    if( state==(1<<(i-1)) )
						dp[state][i]=mat[0][i];
                    else
                    {
                        for(j=1; j<=n; j++)
                            if(j!=i && (state & 1<<(j-1) ) )//枚举不是城市i的其他城市
                                dp[state][i]=min( dp[state][i] , dp[state-(1<<(i-1))][j]+mat[j][i] );
                    }
                }
            }
        int mindis=inf;
        state=( (1<<n)-1 );
        for(i=0; i<=n; i++)
            if(dp[state][i]+mat[i][0]<mindis)
                mindis=dp[state][i]+mat[i][0];
        printf("%d\n",mindis);
    }
    return 0;
}
